#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@his-pc>
#
# Distributed under terms of the MIT license.


"""
每个海岛群类似于无向图中的一个连通分量.
"""


class Solution:
    """
    @param grid: an integer matrix
    @return: an integer
    """
    ISLAND = 1
    CITY = 2
    def numIslandCities(self, grid):
        # Write your code here
        self.rows, self.cols = len(grid), len(grid[0])
        self.visited = self.make_matrix(self.rows, self.cols, False)
        self.grid = grid
        cnts = 0

        for row in range(self.rows):
            for col in range(self.cols):
                if grid[row][col] == 0:
                    continue

                if self.visited[row][col]:
                    continue

                self.is_city = False
                self.dfs_is_city(row, col)
                if self.is_city:
                    cnts += 1

        return cnts

    # =================== dfs  =====================
    def dfs_is_city(self, row, col):
        # 类似于深度搜索求无向图的连通分量: 也可以广度优先bfs
        # 访问row, col的上下左右
        # 0 0 1 1
        # 1 1 1 1

        if row < 0 or row >= self.rows:
            return

        if col < 0 or col >= self.cols:
            return

        if self.grid[row][col] == 0:
            return

        if self.visited[row][col]:
            return

        self.visited[row][col] = True

        val = self.grid[row][col]
        assert val == 1 or val == 2

        if val == self.CITY:
            self.is_city = True

        # 遍历上下左右
        self.dfs_is_city(row-1, col)
        self.dfs_is_city(row+1, col)
        self.dfs_is_city(row, col-1)
        self.dfs_is_city(row, col+1)

    # =================== bfs =====================
    # 不再演示bfs方式

    def make_matrix(self, rows, cols, init_value=None):
        one_row = [init_value] * cols
        return [list(one_row) for i in range(rows)]


def main():
    print("start main")
    s = Solution()

    mat = [
         [1,1,0,0,0],
         [0,1,0,0,1],
         [0,0,2,1,2],
         [0,0,0,0,0],
         [0,0,0,0,2]
    ]
    mat = [
         [1,1,0,0,0],
         [0,1,0,0,1],
         [0,0,0,1,1],
         [0,0,0,0,0],
         [0,0,0,0,1]
    ]
    ret = s.numIslandCities(mat)
    print(ret)

if __name__ == "__main__":
    main()
